4.5 Generate and Test

Generate-and-Test is a very general purpose (though not always efficient) problem-solving method that can be used to solve problems without thinking very hard.

The idea behind generate-and-test is relatively simple: instead of thinking of clever algorithms for solving a problem, just generate all potential answers and test whether any of them are correct! This may not be the most efficient strategy, but it is often easy to express in Prolog, relying on the underlying Depth-First Search.

Example

Suppose we want to know whether any numbers in a some list are between 200 and 500 inclusive.

Rather than search for 200, search for 201, search for 202, etc., we can use a generate-and-test strategy:

has_200_to_500(L) :- member(N, L), between(200, 500, N).

The idea is that given a fixed list L of numbers, the subgoal member(N, L) will pick (“generate”) some number N from the list L, and then the subgoal between(2, 5, N) will test whether that list element is between 200 and 500. If not, Prolog will backtrack and pick a different N from the list.

The code will succeed as soon as member picks a suitable number N from the list; if all elements of the list are tried and none is in the right range, the predicate will fail.

Example

Suppose we want to divide a list of even length into its first half and its second half. We can solve this in one line of Prolog as follows:

equal_split(L, L1, L2) :- append(L1, L2, L), length(L1, N), length(L2, N).

Here, given a list L we use append (“in reverse”) to generate ways of splitting the list into L1 and L2, and then we use length to test whether a split consists of two lists of the same length.

Obviously, this is not terribly efficient, but it is very easy to write. (If we’re mostly interested in splitting small lists or if we don’t intend to use this predicate very often, the simplicity and clarity of the code might make this a better choice than harder-to-understand but more efficient alternatives.)

Example

One of the most famous examples of generate-and-test in Prolog is the one-line definition of sorting:

sort(L, S) :- permutation(L, S), increasing(S).

where we assume there is a predicate increasing that tests whether a list is in increasing order (i.e., whether it is sorted).

Here, to find an S that is a sorted version of a list L, the idea is to simply generate all possible permutations of L and test whether the permutation is sorted.

Obviously this is wildly impractical for long lists (since there are \(n!\) permutations to be tested if the input list has length \(n\)).

But the simplest way to express that any sorting algorithm is correct is to say that the output is a permutation of the input and the output is sorted order. In contrast to most other programming languages Prolog lets us directly execute this declarative specification, if we choose.

(We can implement more efficient sorting algorithms in Prolog, but not with such simple code.)